Path computation for tunnels of a computer network, e.g., label switched paths (LSPs), may be performed by head-end nodes of the tunnels, or by specialized Path Computation Elements (PCEs). For example, tunnels in many Multi-Protocol Label Switching (MPLS) Traffic Engineering (TE) networks (e.g., MPLS TE-LSPs) are computed using a constrained shortest path first (CSPF) algorithm, which offers high flexibility/scalability, and is well-equipped to handle frequent topology changes, dynamic traffic demands, and resource availability changes. While head-end nodes of tunnels may often be equipped to compute a suitable path for a tunnel, PCEs offer a variety of benefits not generally available to head-end nodes. For instance, PCEs may have advanced knowledge of the network topology, such as knowledge of existing tunnels through the network of which the head-end nodes may not be aware, visibility in other domains, etc. In addition, PCEs may be configured to communicate with other PCEs, such as for inter-domain (inter-area and/or inter-Autonomous-System, “inter-domain”) path computation.
Accordingly, a path computation client (PCC), such as a head-end node, may send a request to a locally-reachable PCE to compute a path for a tunnel to one or more desired destinations (e.g., possibly with one or more constraints, as will be understood by those skilled in the art). In situations where a destination is beyond the knowledge of the local PCE, the local PCE may forward the request to a remote (next-hop/downstream) PCE, e.g., in a different domain, to continue the computation of the path; thus the local PCE acts as a PCC to the cooperating remote PCE. The remote PCE may further forward the request to other remote PCEs toward the destination and so on, until a final PCE (local to the destination) is reached. Each remote PCE may then return its local portion of one or more computed paths to its upstream PCE (that is, the PCC from which each PCE received the forwarded request), which may then compute its respective portion based on the received portions of the computed path(s). In this manner, a “path computation chain” or “PCE chain” is established, i.e., along a path of PCEs used to compute the path to the destination (e.g., also referred to as “recursive path computation,” as may be understood by those skilled in the art).
Generally, inter-domain point-to-multipoint (P2MP) paths (i.e., one source and a plurality of destinations across a plurality of domains, also referred to as inter-domain P2MP trees) are particularly difficult to compute, even for a distributed PCE architecture. For instance, while the recursive path computation mentioned above may be well-suited for point-to-point (P2P) paths, P2MP path computation involves multiple branching path segments from the source to the plurality of destinations. As such, inter-domain P2MP path computation may result in a plurality of per-domain path options that may be difficult to coordinate efficiently and effectively between domains. That is, where one or more domains have a plurality of ingress and/or egress border routers, there is currently no known technique for one domain to determine which border routers another domain will utilize for the inter-domain P2MP tree, and to limit the computation of the P2MP tree to those utilized border routers. Also, such per-domain path computation may result in a merging of segments of the P2MP tree, e.g., where two or more diverse segments from one domain are merged in a downstream domain, thus rendering the diverse segments in the upstream domain substantially unnecessary/inefficient (and, as will be understood by those skilled in the art, contrary to the conventional structure and use of a P2MP tree).